Continuous tone images do not print well on most printing devices, so the image is usually printed as a screen or pattern of dots. The screen consists of an array of dots or halftone cells, each of which represents one section of continuous tone in the original image. A halftone cell, in turn, consists of a single dot, relatively larger or smaller to represent darker or lighter portions of the original continuous tone image. On a raster display device, a halftone cell can be displayed as a series of display-device pixels. A dark screen dot or halftone cell will have most of the pixels turned on while a light halftone cell will have most of the pixels turned off. A complete screen of the original image is composed of many such halftone cells, each of which has an independent density of displayed pixels and therefore a different apparent darkness when viewed from a distance.
In printing a color image, it is advantageous to have separate patterns of halftone cells oriented differently for each color. Superimposing two highly periodic and regular patterns with some angular offset, however, can lead to interference patterns, known as moire patterns, which are often shimmering in appearance. One effect, when printed, is bands of color where a flat, even field of color is desired. An additional, independent moire pattern can even be formed by interference between a first moire pattern and a third periodic pattern. Printing angled screens on a raster display device often accentuates moire effects. The screen angle and period must be reproduced very accurately in order to minimize moire patterns. It is well known in the printing industry that these moire patterns can be minimized by printing the color screens at certain angles. One classic screen system used by color printers includes a black screen at 45 degrees from horizontal, cyan at 15 degrees, magenta at 75 (or -15) and yellow at 0, with equal periods (the distance of the regular spacing between the centers of halftone dots in the image). Other useful printing angles and factors that allow one to choose useful printing angles are well known to those skilled in the art.
Previous techniques for creating rotated screens on digital devices were either 1) only able to approximate a small number of screen angle and period combinations without using excessive memory, or 2) took an excessive amount of time when implemented as a computer program. The first type of technique did not easily reproduce the angles used in classic color printing screens. U.S. Pat. No. 4,149,194 (Holladay) claimed one such method for printing rotated screens. The screen grid was described by two integral vectors U and V, e.g. U=(U.sub.x, U.sub.y) where U.sub.x and U.sub.y are integers. The "UV space" defined by the UV coordinate system was regular, but generally at an angle to device space. Under these restraints the number of pixels lying within a halftone cell was integral. In addition, the pixels could be arranged in a shape, typically a rectangle, that was the same for each halftone cell. That shape was repeated over the entire image to "tile" the plane of the image. Each halftone "spot" in the final output corresponds to one halftone cell and can be described by a "spot function." The spot function, described below in more detail, describes a reference value for each halftone cell pixel against which each source pixel is compared to ultimately form a halftone spot. Depending on the darkness of the corresponding source image portion, more or fewer of the display pixels will be displayed in each halftone cell. The halftone level can be precomputed for the pixels in one of these tiles, and then these precomputed values can be fetched directly from memory for pixels falling in other tiles.
This method is fast: once the values for a tile have been computed, the remaining values can be obtained very quickly from memory or special registers. Speed is important since a single image may contain millions to tens of millions of pixels to be processed. The disadvantage of this method is that it can only poorly approximate so-called "irrational" screen angles. For example, if one desires the traditional printing screen angle of 15 degrees, the XY coordinates of vectors U or V cannot both be integral. If the XY coordiantes are rounded to the nearest available integer values then the angle and period of the screen grid will be changed enough so that gross moire patterns will occur when such a screen interacts with other screens.
A second method for computing the halftone level function was claimed in U.S. Pat. Nos. 4,499,489 (Gall) and 4,350,996 (Rosenfeld). The device coordinate system is represented in these patents by XY space and a halftone cell in the screen to be printed is represented by a vector in the UV coordinate system. A displacement of one pixel to the right in XY space can be described as (a.sub.1, b.sub.1) in the (U, V) coordinate system. This precalculated displacement makes it easy to convert a coordinate (X, Y) in device space into UV space if the coordinate (X-1, Y) to the left of (X, Y) already has been calculated. If (X-1, Y) is (a, b) in UV space then (X, Y) is (a+a.sub.1, b+b.sub.1) in UV space. Using this method, after doing the conversion to UV space for the leftmost pixel position in a row of pixels, the conversion for the remaining pixels in that row can be achieved by two additions for each pixel position. It is important to convert pixel positions to the UV coordinate system because the halftone level function can then be easily implemented by calling the spot function with the fractional parts of the coordinates in UV space.
This method is very accurate. Using arithmetic of high enough precision, screens of any angle and frequency can be simulated. This method, however, cannot be as fast as the Holladay method. First of all two additions are required to calculate the coordinates of each pixel in the XY system. Secondly, the spot function must be evaluated at each pixel. This can be speeded up by implementing the spot function as a look-up table, but even that will require some indexing and a memory fetch. Although the number of operations is not great, it is still more than twice that required in the Holladay method.
A method of using threshold matrices to generate halftone images, including certain screen angles, is described in U.S. Pat. No. 4,752,822 (Kawamura). The reading (scanning) and generating (display) devices described therein are generally useful in practicing the present invention as well. The threshold matrix described in Kawamura, however, is of only limited usefulness and can reproduce only limited screen angles and periods.
The technique presented here is an improvement over the prior art in that more angle-period combinations are available and the method can be made to run quickly when implemented as a computer program. Classic screen printing angles were easily, and accurately, reproduced by this system.
One object of this invention is to provide a method for implementing a halftone level function for rotated screens including multiple angle-period combinations and to produce a halftone image formed with a rotated screen on a digital output device.
Another object of this invention is to provide a method of computing halftone screened images that can be made to run quickly when implemented as a computer program.